home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gxstroke.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  43.8 KB  |  1,377 lines
  1. /* Copyright (C) 1989, 1995, 1996, 1997, 1998, 1999 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gxstroke.c,v 1.2 2000/09/19 19:00:40 lpd Exp $ */
  20. /* Path stroking procedures for Ghostscript library */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gpcheck.h"
  24. #include "gserrors.h"
  25. #include "gsdcolor.h"
  26. #include "gxfixed.h"
  27. #include "gxfarith.h"
  28. #include "gxmatrix.h"
  29. #include "gscoord.h"
  30. #include "gsdevice.h"
  31. #include "gxdevice.h"
  32. #include "gxhttile.h"
  33. #include "gxistate.h"
  34. #include "gzline.h"
  35. #include "gzpath.h"
  36. #include "gzcpath.h"
  37. #include "gxpaint.h"
  38.  
  39. /*
  40.  * We don't really know whether it's a good idea to take fill adjustment
  41.  * into account for stroking.  Disregarding it means that strokes
  42.  * come out thinner than fills; observing it produces heavy-looking
  43.  * strokes at low resolutions.  But in any case, we must disregard it
  44.  * when stroking zero-width lines.
  45.  */
  46. #define USE_FILL_ADJUSTMENT
  47.  
  48. #ifdef USE_FILL_ADJUSTMENT
  49. #  define STROKE_ADJUSTMENT(thin, pis, xy)\
  50.      (thin ? fixed_0 : (pis)->fill_adjust.xy)
  51. #else
  52. #  define STROKE_ADJUSTMENT(thin, pis, xy) fixed_0
  53. #endif
  54.  
  55. /*
  56.  * For some reason, we commented out the optimization for portrait,
  57.  * landscape, and uniform (non-scaled) transformations.  We have no record
  58.  * of why we did this, and we don't know what bugs re-enabling it may
  59.  * introduce.
  60.  */
  61. #define OPTIMIZE_ORIENTATION
  62.  
  63. /*
  64.  * Compute the amount by which to expand a stroked bounding box to account
  65.  * for line width, caps and joins.  Return 0 if the result is exact, 1 if
  66.  * it may be conservative, or gs_error_limitcheck if the result is too
  67.  * large to fit in a gs_fixed_point.
  68.  *
  69.  * Because of square caps and miter and triangular joins, the maximum
  70.  * expansion on each side (in user space) is
  71.  *      K * line_width/2
  72.  * where K is determined as follows:
  73.  *      If the path is only a single line segment, K = 1;
  74.  *      if triangular joins, K = 2;
  75.  *      if miter joins, K = miter_limit;
  76.  *      otherwise, K = 1.
  77.  *
  78.  * If the following conditions apply, K = 1 yields an exact result:
  79.  *    - The CTM is of the form [X 0 0 Y] or [0 X Y 0].
  80.  *    - Square or round caps are used, or all subpaths are closed.
  81.  *    - All segments (including the implicit segment created by
  82.  *      closepath) are vertical or horizontal lines.
  83.  *
  84.  * Note that these conditions are sufficient, but not necessary, to get an
  85.  * exact result.  We choose this set of conditions because it is easy to
  86.  * check and covers many common cases.  Clients that care always have the
  87.  * option of using strokepath to get an exact result.
  88.  */
  89. private float join_expansion_factor(P2(const gs_imager_state *, gs_line_join));
  90. int
  91. gx_stroke_path_expansion(const gs_imager_state * pis, const gx_path * ppath,
  92.              gs_fixed_point * ppt)
  93. {
  94.     const subpath *psub = ppath->first_subpath;
  95.     const segment *pseg;
  96.     double cx = fabs(pis->ctm.xx) + fabs(pis->ctm.yx);
  97.     double cy = fabs(pis->ctm.xy) + fabs(pis->ctm.yy);
  98.     double expand = pis->line_params.half_width;
  99.     int result = 1;
  100.  
  101.     /* Check for whether an exact result can be computed easily. */
  102.     if (is_fzero2(pis->ctm.xy, pis->ctm.yx) ||
  103.     is_fzero2(pis->ctm.xx, pis->ctm.yy)
  104.     ) {
  105.     bool must_be_closed =
  106.         !(pis->line_params.cap == gs_cap_square ||
  107.           pis->line_params.cap == gs_cap_round);
  108.     gs_fixed_point prev;
  109.  
  110.     for (pseg = (const segment *)psub; pseg;
  111.          prev = pseg->pt, pseg = pseg->next
  112.          )
  113.         switch (pseg->type) {
  114.         case s_start:
  115.         if (((const subpath *)pseg)->curve_count ||
  116.             (must_be_closed && !((const subpath *)pseg)->is_closed)
  117.             )
  118.             goto not_exact;
  119.         break;
  120.         case s_line:
  121.         case s_line_close:
  122.         if (!(pseg->pt.x == prev.x || pseg->pt.y == prev.y))
  123.             goto not_exact;
  124.         break;
  125.         default:        /* other/unknown segment type */
  126.         goto not_exact;
  127.         }
  128.     result = 0;        /* exact result */
  129.     }
  130. not_exact:
  131.     if (result) {
  132.     if (!gx_path_has_curves(ppath) && gx_path_subpath_count(ppath) <= 1 &&
  133.         (psub == 0 || (pseg = psub->next) == 0 ||
  134.          (pseg = pseg->next) == 0 || pseg->type == s_line_close))
  135.         DO_NOTHING;
  136.     else {
  137.         float factor = join_expansion_factor(pis, pis->line_params.join);
  138.  
  139.         if (pis->line_params.curve_join >= 0)
  140.         factor = max(factor, join_expansion_factor(pis,
  141.                 (gs_line_join)pis->line_params.curve_join));
  142.         expand *= factor;
  143.     }
  144.     }
  145.         
  146.     /* Short-cut gs_bbox_transform. */
  147.     {
  148.     float exx = expand * cx;
  149.     float exy = expand * cy;
  150.     int code = set_float2fixed_vars(ppt->x, exx);
  151.  
  152.     if (code < 0)
  153.         return code;
  154.     code = set_float2fixed_vars(ppt->y, exy);
  155.     if (code < 0)
  156.         return code;
  157.     }
  158.  
  159.     return result;
  160. }
  161. private float
  162. join_expansion_factor(const gs_imager_state *pis, gs_line_join join)
  163. {
  164.     switch (join) {
  165.     case gs_join_miter: return pis->line_params.miter_limit;
  166.     case gs_join_triangle: return 2.0;
  167.     default: return 1.0;
  168.     }
  169. }
  170.  
  171. /*
  172.  * Structure for a partial line (passed to the drawing routine).
  173.  * Two of these are required to do joins right.
  174.  * Each endpoint includes the two ends of the cap as well,
  175.  * and the deltas for square, round, and triangular cap computation.
  176.  *
  177.  * The two base values for computing the caps of a partial line are the
  178.  * width and the end cap delta.  The width value is one-half the line
  179.  * width (suitably transformed) at 90 degrees counter-clockwise
  180.  * (in device space, but with "90 degrees" interpreted in *user*
  181.  * coordinates) at the end (as opposed to the origin) of the line.
  182.  * The cdelta value is one-half the transformed line width in the same
  183.  * direction as the line.  From these, we compute two other values at each
  184.  * end of the line: co and ce, which are the ends of the cap.
  185.  * Note that the cdelta values at o are the negatives of the values at e,
  186.  * as are the offsets from p to co and ce.
  187.  *
  188.  * Initially, only o.p, e.p, e.cdelta, width, and thin are set.
  189.  * compute_caps fills in the rest.
  190.  */
  191. typedef gs_fixed_point *p_ptr;
  192. typedef struct endpoint_s {
  193.     gs_fixed_point p;        /* the end of the line */
  194.     gs_fixed_point co, ce;    /* ends of the cap, p +/- width */
  195.     gs_fixed_point cdelta;    /* +/- cap length */
  196. } endpoint;
  197. typedef endpoint *ep_ptr;
  198. typedef const endpoint *const_ep_ptr;
  199. typedef struct partial_line_s {
  200.     endpoint o;            /* starting coordinate */
  201.     endpoint e;            /* ending coordinate */
  202.     gs_fixed_point width;    /* one-half line width, see above */
  203.     bool thin;            /* true if minimum-width line */
  204. } partial_line;
  205. typedef partial_line *pl_ptr;
  206.  
  207. /* Assign a point.  Some compilers would do this with very slow code */
  208. /* if we simply implemented it as an assignment. */
  209. #define ASSIGN_POINT(pp, p)\
  210.   ((pp)->x = (p).x, (pp)->y = (p).y)
  211.  
  212. /* Other forward declarations */
  213. private bool width_is_thin(P1(pl_ptr));
  214. private void adjust_stroke(P3(pl_ptr, const gs_imager_state *, bool));
  215. private int line_join_points(P6(const gx_line_params * pgs_lp,
  216.                 pl_ptr plp, pl_ptr nplp,
  217.                 gs_fixed_point * join_points,
  218.                 const gs_matrix * pmat, gs_line_join join));
  219. private void compute_caps(P1(pl_ptr));
  220. private int add_points(P4(gx_path *, const gs_fixed_point *,
  221.               int, bool));
  222. private int add_round_cap(P2(gx_path *, const_ep_ptr));
  223. private int cap_points(P3(gs_line_cap, const_ep_ptr,
  224.               gs_fixed_point * /*[3] */ ));
  225.  
  226. /* Define the default implementation of the device stroke_path procedure. */
  227. int
  228. gx_default_stroke_path(gx_device * dev, const gs_imager_state * pis,
  229.                gx_path * ppath, const gx_stroke_params * params,
  230.                const gx_drawing_color * pdcolor,
  231.                const gx_clip_path * pcpath)
  232. {
  233.     return gx_stroke_path_only(ppath, (gx_path *) 0, dev, pis, params,
  234.                    pdcolor, pcpath);
  235. }
  236.  
  237. /* Fill a partial stroked path.  Free variables: */
  238. /* to_path, stroke_path_body, fill_params, always_thin, pis, dev, pdevc, */
  239. /* code, ppath, exit(label). */
  240. #define FILL_STROKE_PATH(thin)\
  241.   if(to_path==&stroke_path_body && !gx_path_is_void(&stroke_path_body)) {\
  242.     fill_params.adjust.x = STROKE_ADJUSTMENT(thin, pis, x);\
  243.     fill_params.adjust.y = STROKE_ADJUSTMENT(thin, pis, y);\
  244.     code = gx_fill_path_only(to_path, dev, pis, &fill_params, pdevc, NULL);\
  245.     gx_path_free(&stroke_path_body, "fill_stroke_path");\
  246.     if ( code < 0 ) goto exit;\
  247.     gx_path_init_local(&stroke_path_body, ppath->memory);\
  248.   }
  249.  
  250. /*
  251.  * Define the internal procedures that stroke a partial_line
  252.  * (the first pl_ptr argument).  If both partial_lines are non-null,
  253.  * the procedure creates an appropriate join; otherwise, the procedure
  254.  * creates an end cap.  If the first int is 0, the procedure also starts
  255.  * with an appropriate cap.
  256.  */
  257. #define stroke_line_proc(proc)\
  258.   int proc(P11(gx_path *, int, pl_ptr, pl_ptr, const gx_device_color *,\
  259.            gx_device *, const gs_imager_state *,\
  260.            const gx_stroke_params *, const gs_fixed_rect *, int,\
  261.            gs_line_join))
  262. typedef stroke_line_proc((*stroke_line_proc_t));
  263.  
  264. private stroke_line_proc(stroke_add);
  265. private stroke_line_proc(stroke_fill);
  266.  
  267. /* Define the orientations we handle specially. */
  268. typedef enum {
  269.     orient_other = 0,
  270.     orient_portrait,        /* [xx 0 0 yy tx ty] */
  271.     orient_landscape        /* [0 xy yx 0 tx ty] */
  272. } orientation;
  273.  
  274. /*
  275.  * Stroke a path.  If to_path != 0, append the stroke outline to it;
  276.  * if to_path == 0, draw the strokes on dev.
  277.  *
  278.  * Note that gx_stroke_path_only with to_path != NULL may clip the path to
  279.  * the clipping path, as for to_path == NULL.  This is almost never
  280.  * what is wanted.
  281.  */
  282. int
  283. gx_stroke_path_only(gx_path * ppath, gx_path * to_path, gx_device * pdev,
  284.            const gs_imager_state * pis, const gx_stroke_params * params,
  285.          const gx_device_color * pdevc, const gx_clip_path * pcpath)
  286. {
  287.     stroke_line_proc_t line_proc =
  288.     (to_path == 0 ? stroke_fill : stroke_add);
  289.     gs_fixed_rect ibox, cbox;
  290.     gx_device_clip cdev;
  291.     gx_device *dev = pdev;
  292.     int code = 0;
  293.     gx_fill_params fill_params;
  294.     const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
  295.     int dash_count = pgs_lp->dash.pattern_size;
  296.     gx_path fpath, dpath;
  297.     gx_path stroke_path_body;
  298.     const gx_path *spath;
  299.     float xx = pis->ctm.xx, xy = pis->ctm.xy;
  300.     float yx = pis->ctm.yx, yy = pis->ctm.yy;
  301.     /*
  302.      * We are dealing with a reflected coordinate system
  303.      * if transform(1,0) is counter-clockwise from transform(0,1).
  304.      * See the note in stroke_add for the algorithm.
  305.      */
  306.     int uniform;
  307.     bool reflected;
  308.     orientation orient =
  309.     (
  310. #ifdef OPTIMIZE_ORIENTATION
  311.      is_fzero2(xy, yx) ?
  312.      (uniform = (xx == yy ? 1 : xx == -yy ? -1 : 0),
  313.       reflected = (uniform ? uniform < 0 : (xx < 0) != (yy < 0)),
  314.       orient_portrait) :
  315.      is_fzero2(xx, yy) ?
  316.      (uniform = (xy == yx ? -1 : xy == -yx ? 1 : 0),
  317.       reflected = (uniform ? uniform < 0 : (xy < 0) == (yx < 0)),
  318.       orient_landscape) :
  319.     /* We should optimize uniform rotated coordinate systems */
  320.     /* here as well, but we don't. */
  321. #endif
  322.      (uniform = 0,
  323.       reflected = xy * yx > xx * yy,
  324.       orient_other));
  325.     /*
  326.      * Formerly, there was a hack here that only treated the joins of
  327.      * flattened curves specially if the dot length was non-zero.
  328.      * This was a surrogate to detect use of the library by PCL
  329.      * interpreters.  We have replaced this hack with an explicit
  330.      * curve join parameter in the graphics state.
  331.      */
  332. #if 0
  333.     segment_notes not_first =
  334.     (!is_fzero(pis->line_params.dot_length) ? sn_not_first : sn_none);
  335. #else
  336.     const segment_notes not_first = sn_not_first;
  337. #endif
  338.     gs_line_join curve_join =
  339.     (pgs_lp->curve_join >= 0 ? (gs_line_join)pgs_lp->curve_join :
  340.      pgs_lp->join == gs_join_none ? gs_join_bevel : pgs_lp->join);
  341.     float line_width = pgs_lp->half_width;    /* (*half* the line width) */
  342.     bool always_thin;
  343.     double line_width_and_scale, device_line_width_scale;
  344.     double device_dot_length = pgs_lp->dot_length * fixed_1;
  345.     const subpath *psub;
  346.  
  347. #ifdef DEBUG
  348.     if (gs_debug_c('o')) {
  349.     int count = pgs_lp->dash.pattern_size;
  350.     int i;
  351.  
  352.     dlprintf3("[o]half_width=%f, cap=%d, join=%d,\n",
  353.           pgs_lp->half_width, (int)pgs_lp->cap, (int)pgs_lp->join);
  354.     dlprintf2("   miter_limit=%f, miter_check=%f,\n",
  355.           pgs_lp->miter_limit, pgs_lp->miter_check);
  356.     dlprintf1("   dash pattern=%d", count);
  357.     for (i = 0; i < count; i++)
  358.         dprintf1(",%f", pgs_lp->dash.pattern[i]);
  359.     dputs(",\n");
  360.     dlprintf4("\toffset=%f, init(ink_on=%d, index=%d, dist_left=%f)\n",
  361.           pgs_lp->dash.offset, pgs_lp->dash.init_ink_on,
  362.           pgs_lp->dash.init_index, pgs_lp->dash.init_dist_left);
  363.     }
  364. #endif
  365.  
  366.     gx_path_bbox(ppath, &ibox);
  367.     /* Expand the path bounding box by the scaled line width. */
  368.     {
  369.     gs_fixed_point expansion;
  370.  
  371.     if (gx_stroke_path_expansion(pis, ppath, &expansion) < 0) {
  372.         /* The expansion is so large it caused a limitcheck. */
  373.         ibox.p.x = ibox.p.y = min_fixed;
  374.         ibox.q.x = ibox.q.y = max_fixed;
  375.     } else {
  376.         expansion.x += pis->fill_adjust.x;
  377.         expansion.y += pis->fill_adjust.y;
  378.         /*
  379.          * It's theoretically possible for the following computations to
  380.          * overflow, so we need to check for this.
  381.          */
  382.         ibox.p.x = (ibox.p.x < min_fixed + expansion.x ? min_fixed :
  383.             ibox.p.x - expansion.x);
  384.         ibox.p.y = (ibox.p.y < min_fixed + expansion.y ? min_fixed :
  385.             ibox.p.y - expansion.y);
  386.         ibox.q.x = (ibox.q.x > max_fixed - expansion.x ? max_fixed :
  387.             ibox.q.x + expansion.x);
  388.         ibox.q.y = (ibox.q.y > max_fixed - expansion.y ? max_fixed :
  389.             ibox.q.y + expansion.y);
  390.     }
  391.     }
  392.     /* Check the expanded bounding box against the clipping regions. */
  393.     if (pcpath)
  394.     gx_cpath_inner_box(pcpath, &cbox);
  395.     else if (pdevc)
  396.     (*dev_proc(dev, get_clipping_box)) (dev, &cbox);
  397.     else {
  398.     /* This is strokepath, not stroke.  Don't clip. */
  399.     cbox = ibox;
  400.     }
  401.     if (!rect_within(ibox, cbox)) {
  402.     /* Intersect the path box and the clip bounding box. */
  403.     /* If the intersection is empty, this call is a no-op. */
  404.     gs_fixed_rect bbox;
  405.  
  406.     if (pcpath) {
  407.         gx_cpath_outer_box(pcpath, &bbox);
  408.         if_debug4('f', "   outer_box=(%g,%g),(%g,%g)\n",
  409.               fixed2float(bbox.p.x), fixed2float(bbox.p.y),
  410.               fixed2float(bbox.q.x), fixed2float(bbox.q.y));
  411.         rect_intersect(ibox, bbox);
  412.     } else
  413.         rect_intersect(ibox, cbox);
  414.     if (ibox.p.x >= ibox.q.x || ibox.p.y >= ibox.q.y) {
  415.         /* Intersection of boxes is empty! */
  416.         return 0;
  417.     }
  418.     /*
  419.      * The path is neither entirely inside the inner clip box
  420.      * nor entirely outside the outer clip box.
  421.      * If we had to flatten the path, this is where we would
  422.      * recompute its bbox and make the tests again,
  423.      * but we don't bother right now.
  424.      *
  425.      * If there is a clipping path, set up a clipping device.
  426.      */
  427.     if (pcpath) {
  428.         gx_make_clip_device(&cdev, gx_cpath_list(pcpath));
  429.         cdev.target = dev;
  430.         cdev.max_fill_band = dev->max_fill_band;
  431.         dev = (gx_device *) & cdev;
  432.         (*dev_proc(dev, open_device)) (dev);
  433.     }
  434.     }
  435.     fill_params.rule = gx_rule_winding_number;
  436.     fill_params.flatness = pis->flatness;
  437. #ifdef USE_FILL_ADJUSTMENT
  438.     fill_params.fill_zero_width =
  439.     (pis->fill_adjust.x | pis->fill_adjust.y) != 0;
  440. #else
  441.     fill_params.fill_zero_width = false;
  442. #endif
  443.     if (line_width < 0)
  444.     line_width = -line_width;
  445.     line_width_and_scale = line_width * (double)int2fixed(1);
  446.     if (is_fzero(line_width))
  447.     always_thin = true;
  448.     else {
  449.     float xa, ya;
  450.  
  451.     switch (orient) {
  452.         case orient_portrait:
  453.         xa = xx, ya = yy;
  454.         goto sat;
  455.         case orient_landscape:
  456.         xa = xy, ya = yx;
  457.           sat:
  458.         if (xa < 0)
  459.             xa = -xa;
  460.         if (ya < 0)
  461.             ya = -ya;
  462.         always_thin = (max(xa, ya) * line_width < 0.5);
  463.         if (!always_thin && uniform) {    /* Precompute a value we'll need later. */
  464.             device_line_width_scale = line_width_and_scale * xa;
  465.         }
  466.         break;
  467.         default:
  468.         {
  469.             /* The check is more complicated, but it's worth it. */
  470.             double xsq = xx * xx + xy * xy;
  471.             double ysq = yx * yx + yy * yy;
  472.             double cross = xx * yx + xy * yy;
  473.  
  474.             if (cross < 0)
  475.             cross = 0;
  476.             always_thin =
  477.             ((max(xsq, ysq) + cross) * line_width * line_width
  478.              < 0.25);
  479.         }
  480.     }
  481.     }
  482.     if_debug7('o', "[o]ctm=(%g,%g,%g,%g,%g,%g) thin=%d\n",
  483.           xx, xy, yx, yy, pis->ctm.tx, pis->ctm.ty, always_thin);
  484.     if (device_dot_length != 0) {
  485.     /*
  486.      * Compute the dot length in device space.  We can't do this
  487.      * quite right for non-uniform coordinate systems; too bad.
  488.      */
  489.     gs_matrix mat;
  490.     const gs_matrix *pmat;
  491.  
  492.     if (pgs_lp->dot_length_absolute) {
  493.         gs_deviceinitialmatrix(pdev, &mat);
  494.         pmat = &mat;
  495.     } else
  496.         pmat = (const gs_matrix *)&pis->ctm;
  497.     device_dot_length *= fabs(pmat->xy) + fabs(pmat->yy);
  498.     }
  499.     /* Start by flattening the path.  We should do this on-the-fly.... */
  500.     if (!gx_path_has_curves(ppath)) {    /* don't need to flatten */
  501.     if (!ppath->first_subpath)
  502.         return 0;
  503.     spath = ppath;
  504.     } else {
  505.     gx_path_init_local(&fpath, ppath->memory);
  506.     if ((code = gx_path_add_flattened_for_stroke(ppath, &fpath,
  507.                         params->flatness, pis)) < 0
  508.         )
  509.         return code;
  510.     spath = &fpath;
  511.     }
  512.     if (dash_count) {
  513.     gx_path_init_local(&dpath, ppath->memory);
  514.     code = gx_path_add_dash_expansion(spath, &dpath, pis);
  515.     if (code < 0)
  516.         goto exf;
  517.     spath = &dpath;
  518.     }
  519.     if (to_path == 0) {
  520.     /* We might try to defer this if it's expensive.... */
  521.     to_path = &stroke_path_body;
  522.     gx_path_init_local(&stroke_path_body, ppath->memory);
  523.     }
  524.     for (psub = spath->first_subpath; psub != 0;) {
  525.     int index = 0;
  526.     const segment *pseg = (const segment *)psub;
  527.     fixed x = pseg->pt.x;
  528.     fixed y = pseg->pt.y;
  529.     bool is_closed = ((const subpath *)pseg)->is_closed;
  530.     partial_line pl, pl_prev, pl_first;
  531.  
  532.     while ((pseg = pseg->next) != 0 &&
  533.            pseg->type != s_start
  534.         ) {
  535.         /* Compute the width parameters in device space. */
  536.         /* We work with unscaled values, for speed. */
  537.         fixed sx = pseg->pt.x, udx = sx - x;
  538.         fixed sy = pseg->pt.y, udy = sy - y;
  539.  
  540.         pl.o.p.x = x, pl.o.p.y = y;
  541.       d:pl.e.p.x = sx, pl.e.p.y = sy;
  542.         if (!(udx | udy)) {    /* degenerate */
  543.         /*
  544.          * If this is the first segment of the subpath,
  545.          * check the entire subpath for degeneracy.
  546.          * Otherwise, ignore the degenerate segment.
  547.          */
  548.         if (index != 0)
  549.             continue;
  550.         /* Check for a degenerate subpath. */
  551.         while ((pseg = pseg->next) != 0 &&
  552.                pseg->type != s_start
  553.             ) {
  554.             sx = pseg->pt.x, udx = sx - x;
  555.             sy = pseg->pt.y, udy = sy - y;
  556.             if (udx | udy)
  557.             goto d;
  558.         }
  559.         /*
  560.          * The entire subpath is degenerate, but it includes
  561.          * more than one point.  If we are using round caps or
  562.          * the dot length is non-zero, draw the caps, otherwise
  563.          * do nothing.
  564.          */
  565.         if (!(pgs_lp->cap == gs_cap_round ||
  566.               pgs_lp->dot_length != 0)
  567.             )
  568.             break;
  569.         /*
  570.          * Orient the dot according to the previous segment if
  571.          * any, or else the next segment if any, or else
  572.          * according to the specified dot orientation.
  573.          */
  574.         {
  575.             const segment *end = psub->prev;
  576.  
  577.             if (end != 0 && (end->pt.x != x || end->pt.y != y))
  578.             sx = end->pt.x, sy = end->pt.y;
  579.             else if (pseg != 0 &&
  580.                  (pseg->pt.x != x || pseg->pt.y != y)
  581.             )
  582.             sx = pseg->pt.x, sy = pseg->pt.y;
  583.         }
  584.         /*
  585.          * Compute the properly oriented dot length, and then
  586.          * draw the dot like a very short line.
  587.          */
  588.         udx = sx - x, udy = sy - y;
  589.         if ((udx | udy) == 0) {
  590.             if (is_fzero(pgs_lp->dot_orientation.xy)) {
  591.             /* Portrait orientation, dot length = X */
  592.             udx = fixed_1;
  593.             } else {
  594.             /* Landscape orientation, dot length = Y */
  595.             udy = fixed_1;
  596.             }
  597.         }
  598.         {
  599.             double scale = device_dot_length /
  600.             hypot((double)udx, (double)udy);
  601.  
  602.             /*
  603.              * If we're using butt caps, make sure the "line" is
  604.              * long enough to show up.
  605.              */
  606.             if (pgs_lp->cap == gs_cap_butt) {
  607.             fixed dmax = max(any_abs(udx), any_abs(udy));
  608.  
  609.             if (dmax * scale < fixed_1)
  610.                 scale = (float)fixed_1 / dmax;
  611.             }
  612.             udx = (fixed) (udx * scale);
  613.             udy = (fixed) (udy * scale);
  614.             if ((udx | udy) == 0)
  615.             udy = fixed_epsilon;
  616.             sx = x + udx;
  617.             sy = y + udy;
  618.         }
  619.         /*
  620.          * Back up 1 segment to keep the bookkeeping straight.
  621.          */
  622.         pseg = (pseg != 0 ? pseg->prev : psub->last);
  623.         goto d;
  624.         }
  625.         if (always_thin) {
  626.         pl.e.cdelta.x = pl.e.cdelta.y = 0;
  627.         pl.width.x = pl.width.y = 0;
  628.         pl.thin = true;
  629.         } else {
  630.         if (uniform != 0) {
  631.             /* We can save a lot of work in this case. */
  632.             /* We know orient != orient_other. */
  633.             float dpx = udx, dpy = udy;
  634.             float wl = device_line_width_scale /
  635.             hypot(dpx, dpy);
  636.  
  637.             pl.e.cdelta.x = (fixed) (dpx * wl);
  638.             pl.e.cdelta.y = (fixed) (dpy * wl);
  639.             /* The width is the cap delta rotated by */
  640.             /* 90 degrees. */
  641.             pl.width.x = -pl.e.cdelta.y,
  642.             pl.width.y = pl.e.cdelta.x;
  643.             pl.thin = false;    /* if not always_thin, */
  644.             /* then never thin. */
  645.  
  646.         } else {
  647.             gs_point dpt;    /* unscaled */
  648.             float wl;
  649.  
  650.             gs_imager_idtransform(pis,
  651.                       (float)udx, (float)udy, &dpt);
  652.             wl = line_width_and_scale /
  653.             hypot(dpt.x, dpt.y);
  654.             /* Construct the width vector in */
  655.             /* user space, still unscaled. */
  656.             dpt.x *= wl;
  657.             dpt.y *= wl;
  658.             /*
  659.              * We now compute both perpendicular
  660.              * and (optionally) parallel half-widths,
  661.              * as deltas in device space.  We use
  662.              * a fixed-point, unscaled version of
  663.              * gs_dtransform.  The second computation
  664.              * folds in a 90-degree rotation (in user
  665.              * space, before transforming) in the
  666.              * direction that corresponds to counter-
  667.              * clockwise in device space.
  668.              */
  669.             pl.e.cdelta.x = (fixed) (dpt.x * xx);
  670.             pl.e.cdelta.y = (fixed) (dpt.y * yy);
  671.             if (orient != orient_portrait)
  672.             pl.e.cdelta.x += (fixed) (dpt.y * yx),
  673.                 pl.e.cdelta.y += (fixed) (dpt.x * xy);
  674.             if (!reflected)
  675.             dpt.x = -dpt.x, dpt.y = -dpt.y;
  676.             pl.width.x = (fixed) (dpt.y * xx),
  677.             pl.width.y = -(fixed) (dpt.x * yy);
  678.             if (orient != orient_portrait)
  679.             pl.width.x -= (fixed) (dpt.x * yx),
  680.                 pl.width.y += (fixed) (dpt.y * xy);
  681.             pl.thin = width_is_thin(&pl);
  682.         }
  683.         if (!pl.thin) {
  684.             adjust_stroke(&pl, pis, false);
  685.             compute_caps(&pl);
  686.         }
  687.         }
  688.         if (index++) {
  689.         gs_line_join join =
  690.             (pseg->notes & not_first ? curve_join : pgs_lp->join);
  691.         int first;
  692.         pl_ptr lptr;
  693.  
  694.         if (join == gs_join_none) {
  695.             /* Fake the end of a subpath so we get */
  696.             /* caps instead of joins. */
  697.             first = 0;
  698.             lptr = 0;
  699.             index = 1;
  700.         } else {
  701.             first = (is_closed ? 1 : index - 2);
  702.             lptr = &pl;
  703.         }
  704.         code = (*line_proc) (to_path, first, &pl_prev, lptr,
  705.                      pdevc, dev, pis, params, &cbox,
  706.                      uniform, join);
  707.         if (code < 0)
  708.             goto exit;
  709.         FILL_STROKE_PATH(always_thin);
  710.         } else
  711.         pl_first = pl;
  712.         pl_prev = pl;
  713.         x = sx, y = sy;
  714.     }
  715.     if (index) {
  716.         /* If closed, join back to start, else cap. */
  717.         gs_line_join join =
  718.         ((pseg == 0 ? (const segment *)spath->first_subpath :
  719.           pseg)->notes & not_first ? curve_join : pgs_lp->join);
  720.         /* For some reason, the Borland compiler requires the cast */
  721.         /* in the following statement. */
  722.         pl_ptr lptr =
  723.         (!is_closed || join == gs_join_none ?
  724.          (pl_ptr) 0 : (pl_ptr) & pl_first);
  725.  
  726.         code = (*line_proc) (to_path, index - 1, &pl_prev, lptr, pdevc,
  727.                  dev, pis, params, &cbox, uniform, join);
  728.         if (code < 0)
  729.         goto exit;
  730.         FILL_STROKE_PATH(always_thin);
  731.     }
  732.     psub = (const subpath *)pseg;
  733.     }
  734.   exit:
  735.     if (to_path == &stroke_path_body)
  736.     gx_path_free(&stroke_path_body, "gx_stroke_path_only error");    /* (only needed if error) */
  737.     if (dash_count)
  738.     gx_path_free(&dpath, "gx_stroke_path exit(dash path)");
  739.   exf:
  740.     if (ppath->curve_count)
  741.     gx_path_free(&fpath, "gx_stroke_path exit(flattened path)");
  742.     return code;
  743. }
  744.  
  745. /* ------ Internal routines ------ */
  746.  
  747. /*
  748.  * Test whether a line is thin, i.e., whether the half-width, measured
  749.  * perpendicular to the line in device space, is less than 0.5 pixel.
  750.  * Unfortunately, the width values we computed are perpendicular to the
  751.  * line in *user* space, so we may have to do some extra work.
  752.  */
  753. private bool
  754. width_is_thin(pl_ptr plp)
  755. {
  756.     fixed dx, dy, wx = plp->width.x, wy = plp->width.y;
  757.  
  758.     /* If the line is horizontal or vertical, things are easy. */
  759.     if ((dy = plp->e.p.y - plp->o.p.y) == 0)
  760.     return any_abs(wy) < fixed_half;
  761.     if ((dx = plp->e.p.x - plp->o.p.x) == 0)
  762.     return any_abs(wx) < fixed_half;
  763.  
  764.     /*
  765.      * If both horizontal and vertical widths are less than
  766.      * 0.5, the line is thin.
  767.      */
  768.     if (any_abs(wx) < fixed_half && any_abs(wy) < fixed_half)
  769.     return true;
  770.  
  771.     /*
  772.      * We have to do this the hard way, by actually computing the
  773.      * perpendicular distance.  The distance from the point (U,V)
  774.      * from a line from (0,0) to (C,D) is
  775.      *      abs(C*V - D*U) / sqrt(C^2 + D^2)
  776.      * In this case, (U,V) is plp->width, and (C,D) is (dx,dy).
  777.      */
  778.     {
  779.     double C = dx, D = dy;
  780.     double num = C * wy - D * wx;
  781.     double denom = hypot(C, D);
  782.  
  783.     /* both num and denom are scaled by fixed_scale^2, */
  784.     /* so we don't need to do any de-scaling for the test. */
  785.     return fabs(num) < denom * 0.5;
  786.     }
  787. }
  788.  
  789. /* Adjust the endpoints and width of a stroke segment */
  790. /* to achieve more uniform rendering. */
  791. /* Only o.p, e.p, e.cdelta, and width have been set. */
  792. private void
  793. adjust_stroke(pl_ptr plp, const gs_imager_state * pis, bool thin)
  794. {
  795.     fixed *pw;
  796.     fixed *pov;
  797.     fixed *pev;
  798.     fixed w, w2;
  799.     fixed adj2;
  800.  
  801.     if (!pis->stroke_adjust && plp->width.x != 0 && plp->width.y != 0)
  802.     return;            /* don't adjust */
  803.     if (any_abs(plp->width.x) < any_abs(plp->width.y)) {
  804.     /* More horizontal stroke */
  805.     pw = &plp->width.y, pov = &plp->o.p.y, pev = &plp->e.p.y;
  806.     adj2 = STROKE_ADJUSTMENT(thin, pis, y) << 1;
  807.     } else {
  808.     /* More vertical stroke */
  809.     pw = &plp->width.x, pov = &plp->o.p.x, pev = &plp->e.p.x;
  810.     adj2 = STROKE_ADJUSTMENT(thin, pis, x) << 1;
  811.     }
  812.     /* Round the larger component of the width up or down, */
  813.     /* whichever way produces a result closer to the correct width. */
  814.     /* Note that just rounding the larger component */
  815.     /* may not produce the correct result. */
  816.     w = *pw;
  817.     w2 = fixed_rounded(w << 1);    /* full line width */
  818.     if (w2 == 0 && *pw != 0) {
  819.     /* Make sure thin lines don't disappear. */
  820.     w2 = (*pw < 0 ? -fixed_1 + adj2 : fixed_1 - adj2);
  821.     *pw = arith_rshift_1(w2);
  822.     }
  823.     /* Only adjust the endpoints if the line is horizontal or vertical. */
  824.     if (*pov == *pev) {
  825.     /* We're going to round the endpoint coordinates, so */
  826.     /* take the fill adjustment into account now. */
  827.     if (w >= 0)
  828.         w2 += adj2;
  829.     else
  830.         w2 = adj2 - w2;
  831.     if (w2 & fixed_1)    /* odd width, move to half-pixel */
  832.         *pov = *pev = fixed_floor(*pov) + fixed_half;
  833.     else            /* even width, move to pixel */
  834.         *pov = *pev = fixed_rounded(*pov);
  835.  
  836.     }
  837. }
  838.  
  839. /* Compute the intersection of two lines.  This is a messy algorithm */
  840. /* that somehow ought to be useful in more places than just here.... */
  841. /* If the lines are (nearly) parallel, return -1 without setting *pi; */
  842. /* otherwise, return 0 if the intersection is beyond *pp1 and *pp2 in */
  843. /* the direction determined by *pd1 and *pd2, and 1 otherwise. */
  844. private int
  845. line_intersect(
  846.           p_ptr pp1,    /* point on 1st line */
  847.           p_ptr pd1,    /* slope of 1st line (dx,dy) */
  848.           p_ptr pp2,    /* point on 2nd line */
  849.           p_ptr pd2,    /* slope of 2nd line */
  850.           p_ptr pi)
  851. {                /* return intersection here */
  852.     /* We don't have to do any scaling, the factors all work out right. */
  853.     float u1 = pd1->x, v1 = pd1->y;
  854.     float u2 = pd2->x, v2 = pd2->y;
  855.     double denom = u1 * v2 - u2 * v1;
  856.     float xdiff = pp2->x - pp1->x;
  857.     float ydiff = pp2->y - pp1->y;
  858.     double f1;
  859.     double max_result = any_abs(denom) * (double)max_fixed;
  860.  
  861. #ifdef DEBUG
  862.     if (gs_debug_c('O')) {
  863.     dlprintf4("[o]Intersect %f,%f(%f/%f)",
  864.           fixed2float(pp1->x), fixed2float(pp1->y),
  865.           fixed2float(pd1->x), fixed2float(pd1->y));
  866.     dlprintf4(" & %f,%f(%f/%f),\n",
  867.           fixed2float(pp2->x), fixed2float(pp2->y),
  868.           fixed2float(pd2->x), fixed2float(pd2->y));
  869.     dlprintf3("\txdiff=%f ydiff=%f denom=%f ->\n",
  870.           xdiff, ydiff, denom);
  871.     }
  872. #endif
  873.     /* Check for degenerate result. */
  874.     if (any_abs(xdiff) >= max_result || any_abs(ydiff) >= max_result) {
  875.     /* The lines are nearly parallel, */
  876.     /* or one of them has zero length.  Punt. */
  877.     if_debug0('O', "\tdegenerate!\n");
  878.     return -1;
  879.     }
  880.     f1 = (v2 * xdiff - u2 * ydiff) / denom;
  881.     pi->x = pp1->x + (fixed) (f1 * u1);
  882.     pi->y = pp1->y + (fixed) (f1 * v1);
  883.     if_debug2('O', "\t%f,%f\n",
  884.           fixed2float(pi->x), fixed2float(pi->y));
  885.     return (f1 >= 0 && (v1 * xdiff >= u1 * ydiff ? denom >= 0 : denom < 0) ? 0 : 1);
  886. }
  887.  
  888. /* Set up the width and delta parameters for a thin line. */
  889. /* We only approximate the width and height. */
  890. private void
  891. set_thin_widths(register pl_ptr plp)
  892. {
  893.     fixed dx = plp->e.p.x - plp->o.p.x, dy = plp->e.p.y - plp->o.p.y;
  894.  
  895. #define TRSIGN(v, c) ((v) >= 0 ? (c) : -(c))
  896.     if (any_abs(dx) > any_abs(dy)) {
  897.     plp->width.x = plp->e.cdelta.y = 0;
  898.     plp->width.y = plp->e.cdelta.x = TRSIGN(dx, fixed_half);
  899.     } else {
  900.     plp->width.y = plp->e.cdelta.x = 0;
  901.     plp->width.x = -(plp->e.cdelta.y = TRSIGN(dy, fixed_half));
  902.     }
  903. #undef TRSIGN
  904. }
  905.  
  906. /* Draw a line on the device. */
  907. /* Treat no join the same as a bevel join. */
  908. private int
  909. stroke_fill(gx_path * ppath, int first, register pl_ptr plp, pl_ptr nplp,
  910.         const gx_device_color * pdevc, gx_device * dev,
  911.         const gs_imager_state * pis, const gx_stroke_params * params,
  912.         const gs_fixed_rect * pbbox, int uniform, gs_line_join join)
  913. {
  914.     const fixed lix = plp->o.p.x;
  915.     const fixed liy = plp->o.p.y;
  916.     const fixed litox = plp->e.p.x;
  917.     const fixed litoy = plp->e.p.y;
  918.  
  919.     if (plp->thin) {
  920.     /* Minimum-width line, don't have to be careful with caps/joins. */
  921.     return (*dev_proc(dev, draw_thin_line))(dev, lix, liy, litox, litoy,
  922.                         pdevc, pis->log_op);
  923.     }
  924.     /* Check for being able to fill directly. */
  925.     {
  926.     const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
  927.     gs_line_cap cap = pgs_lp->cap;
  928.  
  929.     if (!plp->thin && (nplp == 0 || !nplp->thin)
  930.         && ((first != 0 && nplp != 0) || cap == gs_cap_butt
  931.         || cap == gs_cap_square)
  932.         && (join == gs_join_bevel || join == gs_join_miter ||
  933.         join == gs_join_none)
  934.         && (pis->fill_adjust.x | pis->fill_adjust.y) == 0
  935.         && lop_is_idempotent(pis->log_op)
  936.         ) {
  937.         gs_fixed_point points[6];
  938.         int npoints, code;
  939.         fixed ax, ay, bx, by;
  940.  
  941.         npoints = cap_points((first == 0 ? cap : gs_cap_butt),
  942.                  &plp->o, points);
  943.         if (nplp == 0)
  944.         code = cap_points(cap, &plp->e, points + npoints);
  945.         else
  946.         code = line_join_points(pgs_lp, plp, nplp, points + npoints,
  947.                     (uniform ? (gs_matrix *) 0 :
  948.                      &ctm_only(pis)), join);
  949.         if (code < 0)
  950.         goto general;
  951.         /* Make sure the parallelogram fill won't overflow. */
  952. #define SUB_OVERFLOWS(r, u, v)\
  953.   (((r = u - v) ^ u) < 0 && (u ^ v) < 0)
  954.         if (SUB_OVERFLOWS(ax, points[0].x, points[1].x) ||
  955.         SUB_OVERFLOWS(ay, points[0].y, points[1].y) ||
  956.         SUB_OVERFLOWS(bx, points[2].x, points[1].x) ||
  957.         SUB_OVERFLOWS(by, points[2].y, points[1].y)
  958.         )
  959.         goto general;
  960. #undef SUB_OVERFLOWS
  961.         if (nplp != 0) {
  962.         if (join == gs_join_miter) {
  963.             /* Make sure we have a bevel and not a miter. */
  964.             if (!(points[2].x == plp->e.co.x &&
  965.               points[2].y == plp->e.co.y &&
  966.               points[5].x == plp->e.ce.x &&
  967.               points[5].y == plp->e.ce.y)
  968.             )
  969.             goto fill;
  970.         } {
  971.             const gs_fixed_point *bevel = points + 2;
  972.  
  973.             /* Identify which 3 points define the bevel triangle. */
  974.             if (points[3].x == nplp->o.p.x &&
  975.             points[3].y == nplp->o.p.y
  976.             )
  977.             ++bevel;
  978.             /* Fill the bevel. */
  979.             code = (*dev_proc(dev, fill_triangle)) (dev,
  980.                              bevel->x, bevel->y,
  981.                    bevel[1].x - bevel->x, bevel[1].y - bevel->y,
  982.                    bevel[2].x - bevel->x, bevel[2].y - bevel->y,
  983.                             pdevc, pis->log_op);
  984.             if (code < 0)
  985.             return code;
  986.         }
  987.         }
  988.         /* Fill the body of the stroke. */
  989.         return (*dev_proc(dev, fill_parallelogram)) (dev,
  990.                            points[1].x, points[1].y,
  991.                              ax, ay, bx, by,
  992.                              pdevc, pis->log_op);
  993.       fill:
  994.         code = add_points(ppath, points, npoints + code, true);
  995.         if (code < 0)
  996.         return code;
  997.         return gx_path_close_subpath(ppath);
  998.     }
  999.     }
  1000.     /* General case: construct a path for the fill algorithm. */
  1001.  general:
  1002.     return stroke_add(ppath, first, plp, nplp, pdevc, dev, pis, params,
  1003.               pbbox, uniform, join);
  1004. }
  1005.  
  1006. /* Add a segment to the path.  This handles all the complex cases. */
  1007. private int
  1008. stroke_add(gx_path * ppath, int first, pl_ptr plp, pl_ptr nplp,
  1009.        const gx_device_color * pdevc, gx_device * dev,
  1010.        const gs_imager_state * pis, const gx_stroke_params * params,
  1011.        const gs_fixed_rect * ignore_pbbox, int uniform, gs_line_join join)
  1012. {
  1013.     const gx_line_params *pgs_lp = gs_currentlineparams_inline(pis);
  1014.     gs_fixed_point points[8];
  1015.     int npoints;
  1016.     int code;
  1017.     bool moveto_first = true;
  1018.  
  1019.     if (plp->thin) {
  1020.     /* We didn't set up the endpoint parameters before, */
  1021.     /* because the line was thin.  Do it now. */
  1022.     set_thin_widths(plp);
  1023.     adjust_stroke(plp, pis, true);
  1024.     compute_caps(plp);
  1025.     }
  1026.     /* Create an initial cap if desired. */
  1027.     if (first == 0 && pgs_lp->cap == gs_cap_round) {
  1028.     if ((code = gx_path_add_point(ppath, plp->o.co.x, plp->o.co.y)) < 0 ||
  1029.         (code = add_round_cap(ppath, &plp->o)) < 0
  1030.         )
  1031.         return code;
  1032.     npoints = 0;
  1033.     moveto_first = false;
  1034.     } else {
  1035.     if ((npoints = cap_points((first == 0 ? pgs_lp->cap : gs_cap_butt), &plp->o, points)) < 0)
  1036.         return npoints;
  1037.     }
  1038.     if (nplp == 0) {
  1039.     /* Add a final cap. */
  1040.     if (pgs_lp->cap == gs_cap_round) {
  1041.         ASSIGN_POINT(&points[npoints], plp->e.co);
  1042.         ++npoints;
  1043.         if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
  1044.         return code;
  1045.         code = add_round_cap(ppath, &plp->e);
  1046.         goto done;
  1047.     }
  1048.     code = cap_points(pgs_lp->cap, &plp->e, points + npoints);
  1049.     } else if (join == gs_join_round) {
  1050.     ASSIGN_POINT(&points[npoints], plp->e.co);
  1051.     ++npoints;
  1052.     if ((code = add_points(ppath, points, npoints, moveto_first)) < 0)
  1053.         return code;
  1054.     code = add_round_cap(ppath, &plp->e);
  1055.     goto done;
  1056.     } else if (nplp->thin)    /* no join */
  1057.     code = cap_points(gs_cap_butt, &plp->e, points + npoints);
  1058.     else            /* non-round join */
  1059.     code = line_join_points(pgs_lp, plp, nplp, points + npoints,
  1060.                 (uniform ? (gs_matrix *) 0 : &ctm_only(pis)),
  1061.                 join);
  1062.     if (code < 0)
  1063.     return code;
  1064.     code = add_points(ppath, points, npoints + code, moveto_first);
  1065.   done:
  1066.     if (code < 0)
  1067.     return code;
  1068.     return gx_path_close_subpath(ppath);
  1069. }
  1070.  
  1071. /* Add lines with a possible initial moveto. */
  1072. private int
  1073. add_points(gx_path * ppath, const gs_fixed_point * points, int npoints,
  1074.        bool moveto_first)
  1075. {
  1076.     if (moveto_first) {
  1077.     int code = gx_path_add_point(ppath, points[0].x, points[0].y);
  1078.  
  1079.     if (code < 0)
  1080.         return code;
  1081.     return gx_path_add_lines(ppath, points + 1, npoints - 1);
  1082.     } else
  1083.     return gx_path_add_lines(ppath, points, npoints);
  1084. }
  1085.  
  1086. /* ---------------- Join computation ---------------- */
  1087.  
  1088. /* Compute the points for a bevel, miter, or triangle join. */
  1089. /* Treat no join the same as a bevel join. */
  1090. /* If pmat != 0, we must inverse-transform the distances for */
  1091. /* the miter check. */
  1092. private int
  1093. line_join_points(const gx_line_params * pgs_lp, pl_ptr plp, pl_ptr nplp,
  1094.          gs_fixed_point * join_points, const gs_matrix * pmat,
  1095.          gs_line_join join)
  1096. {
  1097. #define jp1 join_points[0]
  1098. #define np1 join_points[1]
  1099. #define np2 join_points[2]
  1100. #define jp2 join_points[3]
  1101. #define jpx join_points[4]
  1102.     /*
  1103.      * Set np to whichever of nplp->o.co or .ce is outside
  1104.      * the current line.  We observe that the point (x2,y2)
  1105.      * is counter-clockwise from (x1,y1), relative to the origin,
  1106.      * iff
  1107.      *  (arctan(y2/x2) - arctan(y1/x1)) mod 2*pi < pi,
  1108.      * taking the signs of xi and yi into account to determine
  1109.      * the quadrants of the results.  It turns out that
  1110.      * even though arctan is monotonic only in the 4th/1st
  1111.      * quadrants and the 2nd/3rd quadrants, case analysis on
  1112.      * the signs of xi and yi demonstrates that this test
  1113.      * is equivalent to the much less expensive test
  1114.      *  x1 * y2 > x2 * y1
  1115.      * in all cases.
  1116.      *
  1117.      * In the present instance, x1,y1 are plp->width,
  1118.      * x2,y2 are nplp->width, and the origin is
  1119.      * their common point (plp->e.p, nplp->o.p).
  1120.      * ccw will be true iff nplp.o.co (nplp.o.p + width) is
  1121.      * counter-clockwise from plp.e.ce (plp.e.p + width),
  1122.      * in which case we want tan(a-b) rather than tan(b-a).
  1123.      *
  1124.      * We make the test using double arithmetic only because
  1125.      * the !@#&^*% C language doesn't give us access to
  1126.      * the double-width-result multiplication operation
  1127.      * that almost all CPUs provide!
  1128.      */
  1129.     bool ccw =
  1130.     (double)(plp->width.x) /* x1 */ * (nplp->width.y) /* y2 */ >
  1131.     (double)(nplp->width.x) /* x2 */ * (plp->width.y) /* y1 */;
  1132.     p_ptr outp, np;
  1133.  
  1134.     /* Initialize for a bevel join. */
  1135.     ASSIGN_POINT(&jp1, plp->e.co);
  1136.     ASSIGN_POINT(&jp2, plp->e.ce);
  1137.  
  1138.     /*
  1139.      * Because of stroke adjustment, it is possible that
  1140.      * plp->e.p != nplp->o.p.  For that reason, we must use
  1141.      * nplp->o.p as np1 or np2.
  1142.      */
  1143.     if (!ccw) {
  1144.     outp = &jp2;
  1145.     ASSIGN_POINT(&np2, nplp->o.co);
  1146.     ASSIGN_POINT(&np1, nplp->o.p);
  1147.     np = &np2;
  1148.     } else {
  1149.     outp = &jp1;
  1150.     ASSIGN_POINT(&np1, nplp->o.ce);
  1151.     ASSIGN_POINT(&np2, nplp->o.p);
  1152.     np = &np1;
  1153.     }
  1154.     if_debug1('O', "[o]use %s\n", (ccw ? "co (ccw)" : "ce (cw)"));
  1155.  
  1156.     /* Handle triangular joins now. */
  1157.     if (join == gs_join_triangle) {
  1158.     fixed tpx = outp->x - nplp->o.p.x + np->x;
  1159.     fixed tpy = outp->y - nplp->o.p.y + np->y;
  1160.  
  1161.     ASSIGN_POINT(&jpx, jp2);
  1162.     if (!ccw) {
  1163.         /* Insert tp between np2 and jp2. */
  1164.         jp2.x = tpx, jp2.y = tpy;
  1165.     } else {
  1166.         /* Insert tp between jp1 and np1. */
  1167.         ASSIGN_POINT(&jp2, np2);
  1168.         ASSIGN_POINT(&np2, np1);
  1169.         np1.x = tpx, np1.y = tpy;
  1170.     }
  1171.     return 5;
  1172.     }
  1173.     /*
  1174.      * Don't bother with the miter check if the two
  1175.      * points to be joined are very close together,
  1176.      * namely, in the same square half-pixel.
  1177.      */
  1178.     if (join == gs_join_miter &&
  1179.     !(fixed2long(outp->x << 1) == fixed2long(np->x << 1) &&
  1180.       fixed2long(outp->y << 1) == fixed2long(np->y << 1))
  1181.     ) {
  1182.     /*
  1183.      * Check whether a miter join is appropriate.
  1184.      * Let a, b be the angles of the two lines.
  1185.      * We check tan(a-b) against the miter_check
  1186.      * by using the following formula:
  1187.      *      If tan(a)=u1/v1 and tan(b)=u2/v2, then
  1188.      *      tan(a-b) = (u1*v2 - u2*v1) / (u1*u2 + v1*v2).
  1189.      *
  1190.      * We can do all the computations unscaled,
  1191.      * because we're only concerned with ratios.
  1192.      * However, if we have a non-uniform coordinate
  1193.      * system (indicated by pmat != 0), we must do the
  1194.      * computations in user space.
  1195.      */
  1196.     float check = pgs_lp->miter_check;
  1197.     double u1 = plp->e.cdelta.y, v1 = plp->e.cdelta.x;
  1198.     double u2 = nplp->o.cdelta.y, v2 = nplp->o.cdelta.x;
  1199.     double num, denom;
  1200.  
  1201.     if (pmat) {
  1202.         gs_point pt;
  1203.  
  1204.         gs_distance_transform_inverse(v1, u1, pmat, &pt);
  1205.         v1 = pt.x, u1 = pt.y;
  1206.         gs_distance_transform_inverse(v2, u2, pmat, &pt);
  1207.         v2 = pt.x, u2 = pt.y;
  1208.         /*
  1209.          * We need to recompute ccw according to the
  1210.          * relative positions of the lines in user space.
  1211.          * We repeat the computation described above,
  1212.          * using the cdelta values instead of the widths.
  1213.          * Because the definition of ccw above is inverted
  1214.          * from the intuitive one (for historical reasons),
  1215.          * we actually have to do the test backwards.
  1216.          */
  1217.         ccw = v1 * u2 < v2 * u1;
  1218. #ifdef DEBUG
  1219.         {
  1220.         double a1 = atan2(u1, v1), a2 = atan2(u2, v2), dif = a1 - a2;
  1221.  
  1222.         if (dif < 0)
  1223.             dif += 2 * M_PI;
  1224.         else if (dif >= 2 * M_PI)
  1225.             dif -= 2 * M_PI;
  1226.         if (dif != 0 && (dif < M_PI) != ccw)
  1227.             lprintf8("ccw wrong: tan(a1=%g)=%g/%g, tan(a2=%g)=%g,%g, dif=%g, ccw=%d\n",
  1228.                  a1, u1, v1, a2, u2, v2, dif, ccw);
  1229.         }
  1230. #endif
  1231.     }
  1232.     num = u1 * v2 - u2 * v1;
  1233.     denom = u1 * u2 + v1 * v2;
  1234.     /*
  1235.      * We will want either tan(a-b) or tan(b-a)
  1236.      * depending on the orientations of the lines.
  1237.      * Fortunately we know the relative orientations already.
  1238.      */
  1239.     if (!ccw)        /* have plp - nplp, want vice versa */
  1240.         num = -num;
  1241. #ifdef DEBUG
  1242.     if (gs_debug_c('O')) {
  1243.         dlprintf4("[o]Miter check: u1/v1=%f/%f, u2/v2=%f/%f,\n",
  1244.               u1, v1, u2, v2);
  1245.         dlprintf3("        num=%f, denom=%f, check=%f\n",
  1246.               num, denom, check);
  1247.     }
  1248. #endif
  1249.     /*
  1250.      * If we define T = num / denom, then we want to use
  1251.      * a miter join iff arctan(T) >= arctan(check).
  1252.      * We know that both of these angles are in the 1st
  1253.      * or 2nd quadrant, and since arctan is monotonic
  1254.      * within each quadrant, we can do the comparisons
  1255.      * on T and check directly, taking signs into account
  1256.      * as follows:
  1257.      *              sign(T) sign(check)     atan(T) >= atan(check)
  1258.      *              ------- -----------     ----------------------
  1259.      *              +       +               T >= check
  1260.      *              -       +               true
  1261.      *              +       -               false
  1262.      *              -       -               T >= check
  1263.      */
  1264.     if (denom < 0)
  1265.         num = -num, denom = -denom;
  1266.     /* Now denom >= 0, so sign(num) = sign(T). */
  1267.     if (check > 0 ?
  1268.         (num < 0 || num >= denom * check) :
  1269.         (num < 0 && num >= denom * check)
  1270.         ) {
  1271.         /* OK to use a miter join. */
  1272.         gs_fixed_point mpt;
  1273.  
  1274.         if_debug0('O', "    ... passes.\n");
  1275.         /* Compute the intersection of */
  1276.         /* the extended edge lines. */
  1277.         if (line_intersect(outp, &plp->e.cdelta, np,
  1278.                    &nplp->o.cdelta, &mpt) == 0
  1279.         )
  1280.         ASSIGN_POINT(outp, mpt);
  1281.     }
  1282.     }
  1283.     return 4;
  1284. }
  1285. /* ---------------- Cap computations ---------------- */
  1286.  
  1287. /* Compute the endpoints of the two caps of a segment. */
  1288. /* Only o.p, e.p, width, and cdelta have been set. */
  1289. private void
  1290. compute_caps(pl_ptr plp)
  1291. {
  1292.     fixed wx2 = plp->width.x;
  1293.     fixed wy2 = plp->width.y;
  1294.  
  1295.     plp->o.co.x = plp->o.p.x + wx2, plp->o.co.y = plp->o.p.y + wy2;
  1296.     plp->o.cdelta.x = -plp->e.cdelta.x,
  1297.     plp->o.cdelta.y = -plp->e.cdelta.y;
  1298.     plp->o.ce.x = plp->o.p.x - wx2, plp->o.ce.y = plp->o.p.y - wy2;
  1299.     plp->e.co.x = plp->e.p.x - wx2, plp->e.co.y = plp->e.p.y - wy2;
  1300.     plp->e.ce.x = plp->e.p.x + wx2, plp->e.ce.y = plp->e.p.y + wy2;
  1301. #ifdef DEBUG
  1302.     if (gs_debug_c('O')) {
  1303.     dlprintf4("[o]Stroke o=(%f,%f) e=(%f,%f)\n",
  1304.           fixed2float(plp->o.p.x), fixed2float(plp->o.p.y),
  1305.           fixed2float(plp->e.p.x), fixed2float(plp->e.p.y));
  1306.     dlprintf4("\twxy=(%f,%f) lxy=(%f,%f)\n",
  1307.           fixed2float(wx2), fixed2float(wy2),
  1308.           fixed2float(plp->e.cdelta.x),
  1309.           fixed2float(plp->e.cdelta.y));
  1310.     }
  1311. #endif
  1312. }
  1313.  
  1314. #define px endp->p.x
  1315. #define py endp->p.y
  1316. #define xo endp->co.x
  1317. #define yo endp->co.y
  1318. #define xe endp->ce.x
  1319. #define ye endp->ce.y
  1320. #define cdx endp->cdelta.x
  1321. #define cdy endp->cdelta.y
  1322.  
  1323. /* Add a round cap to a path. */
  1324. /* Assume the current point is the cap origin (endp->co). */
  1325. private int
  1326. add_round_cap(gx_path * ppath, const_ep_ptr endp)
  1327. {
  1328.     int code;
  1329.  
  1330.     /*
  1331.      * Per the Red Book, we draw a full circle, even though a semicircle
  1332.      * is sufficient for the join.
  1333.      */
  1334.     if ((code = gx_path_add_partial_arc(ppath, px + cdx, py + cdy,
  1335.                     xo + cdx, yo + cdy,
  1336.                     quarter_arc_fraction)) < 0 ||
  1337.     (code = gx_path_add_partial_arc(ppath, xe, ye, xe + cdx, ye + cdy,
  1338.                     quarter_arc_fraction)) < 0 ||
  1339.     (code = gx_path_add_partial_arc(ppath, px - cdx, py - cdy,
  1340.                     xe - cdx, ye - cdy,
  1341.                     quarter_arc_fraction)) < 0 ||
  1342.     (code = gx_path_add_partial_arc(ppath, xo, yo, xo - cdx, yo - cdy,
  1343.                     quarter_arc_fraction)) < 0 ||
  1344.     /* The final point must be (xe,ye). */
  1345.     (code = gx_path_add_line(ppath, xe, ye)) < 0
  1346.     )
  1347.     return code;
  1348.     return 0;
  1349. }
  1350.  
  1351. /* Compute the points for a non-round cap. */
  1352. /* Return the number of points. */
  1353. private int
  1354. cap_points(gs_line_cap type, const_ep_ptr endp, gs_fixed_point *pts /*[3]*/)
  1355. {
  1356. #define PUT_POINT(i, px, py)\
  1357.   pts[i].x = (px), pts[i].y = (py)
  1358.     switch (type) {
  1359.     case gs_cap_butt:
  1360.         PUT_POINT(0, xo, yo);
  1361.         PUT_POINT(1, xe, ye);
  1362.         return 2;
  1363.     case gs_cap_square:
  1364.         PUT_POINT(0, xo + cdx, yo + cdy);
  1365.         PUT_POINT(1, xe + cdx, ye + cdy);
  1366.         return 2;
  1367.     case gs_cap_triangle:    /* (not supported by PostScript) */
  1368.         PUT_POINT(0, xo, yo);
  1369.         PUT_POINT(1, px + cdx, py + cdy);
  1370.         PUT_POINT(2, xe, ye);
  1371.         return 3;
  1372.     default:        /* can't happen */
  1373.         return_error(gs_error_unregistered);
  1374.     }
  1375. #undef PUT_POINT
  1376. }
  1377.